#pragma once
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <stdexcept>
#include <memory>
#include <climits>

const int INFINITY = INT_MAX / 2 - 1;
struct edge{
   int from;
   int to;
   int weight;
   edge(int from, int to, int weight) : from(from), to(to),  weight(weight) {}
   bool operator < (const edge tmp) const{
       if(from < tmp.from) return true;
       if(from == tmp.from) return (to < tmp.to);
       return false;
   }
   bool operator == (const edge tmp)const{
       return(from == tmp.from && to == tmp.to && weight == tmp.weight);
   }
   edge(){}
};

class Graph{
private:

public:
   virtual int GetNumberOfVertices() const = 0;
   virtual std::vector < edge > GetIncidentEdges(int vertex)const = 0;
   virtual ~Graph() {};
   virtual int GetEdgeWeight(int from, int to) const = 0;
};

struct ConnectivityMatrix : public Graph{
private:
   std::vector < std::vector < int > > matrix;
   int vertices_number;
    
public:
   
   int GetNumberOfVertices()const{ return vertices_number;}
   
   int GetEdgeWeight(int from, int to)const{
       return matrix[from][to];
   }
   
   ConnectivityMatrix(const int vertices_nmbr, const std::vector < edge > &edges){
       vertices_number = vertices_nmbr;
       matrix.resize(vertices_number, std::vector<int>(vertices_number, INFINITY));
       for(int  current = 0; current < edges.size(); current++){
           edge current_edge = edges[current];
           int from = current_edge.from;
           int to = current_edge.to;
           if(from < vertices_number && to < vertices_number) matrix[from][to] = current_edge.weight;
           else {
               throw std::logic_error("bad edges");
           }
       }
   }
   
    std::vector < edge > GetIncidentEdges(int vertex)const{
       std::vector <edge > result;
       for(int current_vertex = 0; current_vertex < vertices_number; current_vertex++){
           if(matrix[vertex][current_vertex] != INFINITY) {
               edge new_edge (vertex, current_vertex, matrix[vertex][current_vertex]);
               result.push_back(new_edge);
           }
       }
       return result;
   }
};
   




struct ConnectivityList : public Graph{
private:
    std:: vector < int > beginnings;
    std::vector < int > ends_of_edges;
    int vertices_number;
    int edges_number;
    std::vector<int>  weights;
public:
    
    int GetNumberOfVertices()const{ return vertices_number;}
    
    
    ConnectivityList(int number_of_vertices, const std::vector < edge > &edges){
        vertices_number = number_of_vertices;
        edges_number = edges.size();
        beginnings.resize(vertices_number, 0);
        for(int edge_number = 0; edge_number < edges.size(); edge_number++){
            edge current_edge = edges[edge_number];
            ends_of_edges.insert(ends_of_edges.begin() + beginnings[current_edge.from], current_edge.to);
            weights.insert(weights.begin() + beginnings[current_edge.from], current_edge.weight);
            for(int vertex = current_edge.from + 1; vertex < vertices_number; vertex++){
                beginnings[vertex]++;
            }
        }
    }
    
    std::vector < edge > GetIncidentEdges(int vertex)const{
        std::vector < int >::const_iterator begin = ends_of_edges.begin() + beginnings[vertex];
        std::vector <int> ::const_iterator begin_weight = weights.begin() + beginnings[vertex];
        std::vector < int > ::const_iterator end;
        std::vector< int > ::const_iterator end_weight;
        if ( vertex == vertices_number - 1){
            end = ends_of_edges.end();
            end_weight = weights.end();
        }
        else {
            end = ends_of_edges.begin() + beginnings[vertex + 1];
            end_weight = weights.begin() + beginnings[vertex + 1];
        }
        std::vector <int> result_ends;
        result_ends.assign(begin, end);
        std::vector<int> result_weights;
        result_weights.assign(begin_weight, end_weight);
        std::vector <edge> result;
        for(int index = 0; index < result_ends.size(); index++){
            edge new_edge (vertex, result_ends[index], result_weights[index]);
            result.push_back(new_edge);
        }
        return result;
    }
    
    int GetEdgeWeight(int from, int to) const{
        int begin = beginnings[from];
        int end;
        if(from == vertices_number - 1){
            end = ends_of_edges.size();
        }
        else {
            end = beginnings[from + 1];
        }
        for(int index = begin; index < end; index++){
            if(ends_of_edges[index] == to){
                return weights[index];
            }
        }
        return INFINITY;
    }


    
  
     ~ConnectivityList() {}
};	

inline std::auto_ptr<Graph> MakeCompactGraph(int number_of_vertices, std::vector <edge> &edges){
    int number_of_edges = edges.size();
    if( (number_of_vertices * number_of_vertices) > (number_of_vertices + 2 * number_of_edges) ){
       return std::auto_ptr<Graph>(new ConnectivityList(number_of_vertices, edges));
    }
    else {
        return std::auto_ptr<Graph>( new ConnectivityMatrix(number_of_vertices, edges));
    }
}


